package algorithm.sort;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 面试题：同学面试腾讯的时候被问到：王者荣耀用户上亿，如何快速的从亿级数据量中找出排名榜首的几位玩家？
 * <p>
 * 思路：用前K个数建个小堆，然后向后遍历其余数，凡是遇到比堆根节点大的，就替换根节点，
 * 然后向下调整，使之始终保持小堆，然后继续遍历，直至访问完数据。这样就将前K个大的数据全放在了堆中。
 * <p>
 * 时间复杂度：建堆+遍历（KlgK+(N-K)lgN） -> NlgK
 */
public class TopNSort {
    public static void main(String[] args) {
        int[] array = {1, 5, 3, 9, 7, 8, 6, 2, 4};
        ArrayList<Integer> res = findLeastK(array, 3);
        System.out.println(res);
        ArrayList<Integer> res2 = findLeastK_priorityQueue(array, 3);
        System.out.println(res2);
    }

    //思路1：堆排序
    public static ArrayList<Integer> findLeastK(int[] array, int k) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        int[] temp = new int[k];
        for (int i = 0; i < k; i++) {
            temp[i] = array[i];
        }
        for (int i = k / 2; i >= 0; i--) {
            adjustHeap(temp, i, k - 1);
        }
        for (int j = k; j < array.length; j++) {
            if (temp[0] > array[j]) {  //存在更小的数字
                temp[0] = array[j];
                adjustHeap(temp, 0, k - 1); //重新调整堆
            }
        }
        for (int i = 0; i < k; i++) {
            res.add(temp[i]);
        }
        return res;
    }

    private static void adjustHeap(int[] array, int start, int end) {
        int temp = array[start];
        int child = start * 2 + 1;
        while (child <= end) {
            if (child + 1 <= end && array[child + 1] > array[child]) {
                child++;
            }
            if (array[child] < temp) {  //如果所有的孩子节点都小于父节点，就结束循环
                break;
            } else {
                array[start] = array[child];
                start = child; //迭代
                child = child * 2 + 1;
            }
        } //end while
        array[start] = temp;
    }

    /**
     * 交换元素
     */
    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    // 思路2:使用priorityQueue
    public static ArrayList<Integer> findLeastK_priorityQueue(int[] input, int k) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        int length = input.length;
        if (k > length || k == 0) {
            return result;
        }

        //priorityQueue默认为小根堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k, Comparator.reverseOrder());
        for (int j : input) {
            if (maxHeap.size() != k) {
                maxHeap.offer(j);
            } else if (maxHeap.peek() > j) {
                Integer temp = maxHeap.poll();
                temp = null;
                maxHeap.offer(j);
            }
        }

        result.addAll(maxHeap);

        return result;
    }
}
